package com.darrenchan.leetcode;

import java.util.Arrays;

/**
 * @Desc
 * @Author chenchi03
 * @CreateTime 2020-02-10 00:05
 */
public class Q1143 {
    public int longestCommonSubsequence(String text1, String text2) {
        if (text1 == null || text1.length() == 0 || text2 == null || text2.length() == 0) {
            return 0;
        }

        char[] s1 = text1.toCharArray();
        char[] s2 = text2.toCharArray();
        int m = s1.length, n = s2.length;

        int[][] dp = new int[m + 1][n + 1];
        int[][] pi = new int[m + 1][n + 1];

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                if (dp[i][j] == dp[i - 1][j]) {
                    pi[i][j] = 0;
                }
                if (dp[i][j] == dp[i][j - 1]) {
                    pi[i][j] = 1;
                }

                if (s1[i - 1] == s2[j - 1]) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - 1] + 1);
                    if (dp[i][j] == dp[i - 1][j - 1] + 1) {
                        pi[i][j] = 2;
                    }
                }
            }
        }

        StringBuilder path = new StringBuilder();
        int i = m, j = n;
        while (i > 0 && j > 0) {
            if (pi[i][j] == 0) {
                i--;
            } else if (pi[i][j] == 1) {
                j--;
            } else if (pi[i][j] == 2) {
                path.insert(0, s1[i - 1]);
                i--;
                j--;
            }
        }

        System.out.println(path.toString());
        System.out.println(dp[m][n]);
        return dp[m][n];
    }

    public static void main(String[] args) {
        new Q1143().longestCommonSubsequence("dsdsdchenchi23243", "1c2h3e4n5c6h7i88fd");
    }
}
